package NiuKe.Tree;
//bit二叉树
import sun.net.www.protocol.http.ntlm.NTLMAuthentication;

import javax.swing.plaf.basic.BasicTreeUI;
import java.util.*;

class  BTnode{//通用模板
    public int val;
    public BTnode left;//左孩子的引用
    public BTnode right;//右孩子的引用
    // private Binarytree parent;//当前父亲结点得引用。
    public BTnode(int val) {
        this.val = val;
    }
}
public class Binarytree {

    public BTnode root;//二叉树的根节点

//    传过来一个先序遍历要求创建一个二叉树，
    private static int i=0;
    public static BTnode preCreate( String str){
       BTnode root=null;
       if (str.charAt(i) != '#'){
           root=new BTnode(str.charAt(i));
           i++;
           root.left=preCreate(str);
           root.right=preCreate(str);
       }else {
           //遇到#号说明空树，直接++
           i++;
       }
       return root;
    }

    public BTnode CreateTree(){
        //穷举的方式创建的，太low了
        BTnode A=new BTnode('A');
        BTnode B=new BTnode('B');
        BTnode C=new BTnode('C');
        BTnode D=new BTnode('D');
        BTnode E=new BTnode('E');
        BTnode F=new BTnode('F');
        BTnode G=new BTnode('G');
        BTnode H=new BTnode('H');
        A.left=B;
        A.right=C;
        B.left=D;
        B.right=E;
        C.left=F;
        C.right=G;
        E.right=H;
        return A;
    }

    // 前序遍历
    public void preOrder(BTnode root){
        if (root == null){
            return;
        }
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }
    //前序非递归的写法
    public void NopreOrder(BTnode root){
        Stack<BTnode> stack=new Stack<>();
        BTnode cur=root;
        while (cur!=null||!stack.isEmpty()) {
            //思想遍历完左子树的时候,让他进入右子树.
            while (cur != null) {
                stack.push(cur);
                System.out.print(cur.val + " ");
                cur = cur.left;
            }
            BTnode top = stack.pop();
            cur = top.right;
        }
    }

    // 中序遍历
    public void inOrder(BTnode root){
        if (root == null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);

    }
    public void NoinOrder(BTnode root){
        // 中序遍历非递归写法
        Stack<BTnode> stack=new Stack<>();
        BTnode cur=root;
        while (cur!=null||!stack.isEmpty()) {
            //思想遍历完左子树的时候,让他进入右子树.
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            BTnode top = stack.pop();
            System.out.print(top.val + " ");
            cur = top.right;
        }
    }

    // 后序遍历
    public void postOrder(BTnode root){
        if (root == null){
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");

    }
    public void NopostOrder(BTnode root){
        // 后序遍历非递归写法
        Stack<BTnode> stack=new Stack<>();
        BTnode cur=root;
        BTnode prev=null;//用来判断打印过没
        while (cur!=null||!stack.isEmpty()) {
            //思想遍历完左子树的时候,让他进入右子树.
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            BTnode top = stack.peek();//不能出栈顶,只能获取
            //如果当前右子树被遍历过直接弹出.
            if (top.right==null||prev ==top.right){
                stack.pop();
                System.out.println(top.val);
                prev=top;//记录一下最近打印的节点
            }else{
                cur = top.right;
            }

        }
    }
//    层序遍历
    public void levelOrder(BTnode root){
        if (root == null)return;
        Queue<BTnode> queue=new LinkedList<>();
        queue.offer(root);
//        注意要判断队列是否为空
        while (!queue.isEmpty()){
            BTnode cur=queue.poll();
            System.out.print(cur.val+" ");
            if (cur.left !=null)queue.offer(cur.left);
            if (cur.right!=null)queue.offer(cur.right);
        }
    }

    /*private List<List<Integer>> levelOrder2(BTnode root){
        List<List<Integer>> ret=new ArrayList<>();
        if (root==null)return ret;
        Queue<BTnode> queue=new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()){
            int size=queue.size();//这个值代表当前层有多少个节点
            List<Integer> list=new ArrayList<>();
            while (size != 0){
                BTnode cur=queue.poll();
                list.add(cur.val);
                if (cur.left !=null)queue.offer(cur.left);
                if (cur.right!=null)queue.offer(cur.right);
                size--;
            }
             arrayList.add(list1);
        }
        return ret;
    }*/

    //获取树中结点的个数
    public int size(BTnode root){
        if (root == null){
            return 0;
        }
        //俩种办法 1：定义一个全局变量-遍历思路
        //2: 子问题思路，让返回值利用起来，每次返回值+1；
//        int count=1;//过了上面，说明至少有个根节点所以count为1
//        count+= size(root.left);
//        count+= size(root.right);
//        return  count;//好理解
//        俩种写法效果一样
        return size(root.left)+size(root.right)+1;//精简
    }


    //返回叶子节点数目
    //遍历写法
    int LeafNodeCount=0;
    public int  getLeafNodeCount(BTnode root){
        if (root == null){
            return 0;
        }
      if (root.left == null && root.right == null){
          LeafNodeCount++;
      }
      getLeafNodeCount(root.left);
      getLeafNodeCount(root.right);
       return LeafNodeCount;
    }
    //子问题思路
    public int  getLeafNodeCount2(BTnode root){
        if (root == null){
            return 0;
        }
        if (root.left == null && root.right == null){
            return 1;
        }
        return getLeafNodeCount2(root.left)+getLeafNodeCount2(root.right);
    }

    /*
    求第K层结点的个数
    */
    public int getKLevelNodeCount(BTnode root,int k){
       //不能简单的用2^（k-1）这个公式来求，因为不是每一层都是满的
       //那就用K来实现判断
        if (root == null || k <= 0){
            return 0;
        }
        if (k == 1){
            return 1;
        }
        return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1);
    }

//    获取二叉树的高度
    //时间复杂度O（N），空间复杂度O（logN）
    public  int getHeight(BTnode root){
        if (root == null){
            return 0;
        }
        int leftHeight=getHeight(root.left);
        int rightHeight=getHeight(root.right);
        return leftHeight>rightHeight?leftHeight+1:rightHeight+1;
    }

    //查找某一个结点的值
//    运用遍历思想
    BTnode find1;
    BTnode find(BTnode root,char k){
        if (root == null){
            return null;
        }
        if (root.val ==k){
          find1=root;
        }
        find(root.left,k);
        find(root.right,k);
        return find1;
    }
//    运用子问题思想
    public  BTnode find2(BTnode root,char k){
        if (root == null){
            return null;
        }
        if (root.val ==k){
            return root;
        }
        BTnode ret=find2(root.left,k);
        if (ret != null){
            return ret;
        }
        ret=find2(root.right,k);
        if (ret != null){
            return ret;
        }
        return null;
    }
//     判断一棵树是不是完全二叉树——运用层序遍历
//    先将根节点压入队列中，然后从队列中出来一个元素，在将从队列中出来的左右子树压入队列中
    public boolean isCompleteTree(BTnode root){
        if (root == null) {return  true;}
        Queue<BTnode> queue=new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            BTnode cur=queue.poll();
            if (cur!=null){
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else {
                break;
            }
        }
        while (!queue.isEmpty()){
           if( queue.poll()!=null){
                return false;
            }else{
               queue.poll();
           }
        }
        return true;
    }

//    判断俩个树是不是相同的二叉树
//    时间复杂度：O（min(m+n))。空间复杂度：O(min(m+n))
    public boolean isSameTree(BTnode p ,BTnode q){
        if (p == null && q!= null || p!=null && q== null){
            //一个为空一个不为空的情况
            return false;
        }
        if (p== null && q==null){
            //判断是否都为空
           return true;
        }
        if (p.val !=q.val){
           //俩个值不相等的情况
           return false;
        }
        return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }

//    判断一颗树是不是另外一颗树的子树:利用上面是不是相同的树
//    时间复杂度：O（m*n)。空间复杂度：O(m*n)
    public boolean isSubtree(BTnode root ,BTnode subroot){
        if (root == null || subroot== null)return false;//好像不写也行。。。

        if (isSameTree(root,subroot))return true;
        if (isSubtree(root.left,subroot))return true;
        if (isSubtree(root.right,subroot))return true;
        return false;
    }
//    判断一棵树是不是平衡二叉树（左子树和右子树的高度最多差1）
//    时间复杂度O（N^2)----高度重复计算了
    public boolean isBalanced(BTnode root){
        if (root==null)return false;
        int legtHeight=getHeight(root.left);
        int rightHeight=getHeight(root.right);
        //如果高度相差小于1且左右子树都是平衡二叉树才对
        return Math.abs(legtHeight-rightHeight) <= 1&& isBalanced(root.left) && isBalanced(root.right);
    }
    //第二种解法-时间复杂度O(N)
    private   int Height(BTnode root){
        if (root == null){
            return 0;
        }
        int leftHeight=Height(root.left);
        int rightHeight=Height(root.right);
        if (leftHeight>=0 && rightHeight>=0&& Math.abs(leftHeight-rightHeight)<=1){
            return Math.max(leftHeight,rightHeight)+1;
        }else {
            //说明不平衡
            return -1;
        }
    }
    public boolean isBalanced2(BTnode root){
        if (root==null)return false;
        return Height(root)>=0;
    }
    //给你一个二叉树的根节点 root ， 检查它是否轴对称。
    //利用判断二叉树是否相同的思想来做
    private boolean isSameTree2(BTnode p ,BTnode q){
        //一个为空一个不为空的情况
        if (p == null && q!= null || p!=null && q== null) return false;
        //判断是否都为空
        if (p== null && q==null) return true;
        //俩个值不相等的情况
        if (p.val !=q.val)return false;
        //p的左子树等于q的右子树,对称么
        return isSameTree(p.left,q.right)&&isSameTree(p.right,q.left);
    }
    public boolean isSymmetric(BTnode root) {
        boolean flag;
        flag=isSameTree2(root.left,root.right);
        return flag;
    }
//    给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
    //做题步骤，1读懂题
//    解题思路：1如果给定的树是一颗二叉搜索树（每棵树根的左边都比根小，跟的右边都比根大）
//    二叉搜索树的特点：中序遍历的大小是有序的
//    写出所有可能的情况然后递归
    /*1：利用二叉搜索树的思路来寻找*/
    public BTnode lowestCommonAncestor( BTnode root,  BTnode p,  BTnode q) {
        if(root == null)return null;
        if(root==p || root==q)return root;
    //    定义俩个左右来递归寻找，不过为什么不能定义全局变量呢？
        BTnode tmp=lowestCommonAncestor(root.left,p,q);
        BTnode tmp2=lowestCommonAncestor(root.right,p,q);
        if(tmp!=null&&tmp2!=null)return root;
        else if(tmp!=null)return tmp;
        else return tmp2;
    }
    /*2：假设这个二叉树使用孩子双亲表示法来表示的，每个节点保存它的父亲节点
    * 解题思路：求链表求交点：利用俩个栈来模拟有双亲节点来实现。
    * 求栈的大小
    * 让栈中多的元素出差值，然后在依次出栈知道栈顶元素相同，此时为公共祖先
    * 难点：怎么找指定路径*/
    //root根节点，node指定节点，stack存放找指定节点的路径
        public boolean getpath(BTnode root, BTnode node, Stack<BTnode> stack){
            if (root == null||node==null)return false;
            stack.push(root);
            if (root == null){
                return true;
            }
            boolean falg=getpath(root.left,node,stack);
            if (falg == true){
                return true;
            }
            falg=getpath(root.right,node,stack);
            if (falg==true){
                return true;
            }
            stack.pop();
            return false;
        }

        public BTnode LowestCommonAncestor2( BTnode root,  BTnode p,  BTnode q) {
            if (root == null) {
                return null;
            }
            Stack<BTnode> stack1 = new Stack<>();
            getpath(root, p, stack1);
            Stack<BTnode> stack2 = new Stack<>();
            getpath(root, q, stack2);
            int size1 = stack1.size();
            int size2 = stack2.size();

            if (size1 > size2) {
                int size = size1 - size2;
                while (size != 0) {
                    stack1.pop();
                    size--;
                }
                while (!stack1.isEmpty() && !stack2.isEmpty()) {
                    if (stack1.peek() == stack2.peek()) {
                        return stack1.pop();
                    } else {
                        stack1.pop();
                        stack2.pop();
                    }
                }
            } else {
                if (size2 > size1) {
                    int size = size2 - size1;
                    while (size != 0) {
                        stack2.pop();
                        size--;
                    }
                    while (!stack1.isEmpty() && !stack2.isEmpty()) {
                        if (stack1.peek() == stack2.peek()) {
                            return stack1.pop();
                        } else {
                            stack1.pop();
                            stack2.pop();
                        }
                    }
                }
            }
            return null;
        }

        /*二叉搜索树转换为双向链表
        * 解题思路：利用中序遍历
        * 将二叉树的左子树转换为前驱，二叉树的右子树转换为后继*/
        private  BTnode prev=null;
        private void  InOrder(BTnode pCur){
            if (pCur == null)return;
            InOrder(pCur.left);
            pCur.left=prev;
            if (prev!=null){
                prev.right=pCur;
            }
            prev=pCur;
            InOrder(pCur.right);
       }
        public BTnode Convert(BTnode pRootOfTree){
            if (pRootOfTree == null)return null;
            InOrder(pRootOfTree);
            BTnode head=pRootOfTree;
            while (head.left!=null){
                head= head.left;
            }
            return head;
        }






//    给你二叉树的根节点 root ，请你采用前序遍历的方式，
//    将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。
    public void  treeToString(BTnode t,StringBuilder sb){
            if (t==null)return;
            sb.append(t.val);
            if (t.left!=null){
                sb.append('(');
                treeToString(t.left,sb);
                sb.append(')');
            }else{
                if (t.right==null){
                   return;
                }else{
                sb.append("()");
                }
            }
        if (t.right==null){
            return;
        }else{
            sb.append('(');
            treeToString(t.right,sb);
            sb.append(')');
        }
    }
    public String tree2str(BTnode root) {
       if (root==null)return null;
       StringBuilder sb=new StringBuilder();
       treeToString(root,sb);
       return sb.toString();
    }
    /*从前序与中序遍历序列构造二叉树
    1：将先序遍历pi下标的元素创建为root
    2:在中序遍历的数组当中，找到pi下标的元素，存在的位置ri
    3：root.left=
       root.right=
    * */
     public int preIndex = 0;

    public TreeNode createTreeByPandI(int[] preorder, int[] inorder,int inbegin,int inend) {

        if(inbegin > inend) {
            //如果满足这个条件  说明 没有左树 或者 右树了
            return null;
        }
        TreeNode root = new TreeNode(preorder[preIndex]);
        //找到根在中序遍历的位置
        int rootIndex = findIndexOfI(inorder,inbegin,inend,preorder[preIndex]);
        if(rootIndex == -1) {
            return null;
        }
        preIndex++;
        //分别创建 左子树 和 右子树
        root.left = createTreeByPandI(preorder,inorder,inbegin,rootIndex-1);
        root.right = createTreeByPandI(preorder,inorder,rootIndex+1,inend);
        return root;
    }

    private int findIndexOfI(int[] inorder,int inbegin,int inend,int key) {

        for(int i = inbegin; i <= inend;i++) {
            if(inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null || inorder == null) return null;

        return createTreeByPandI(preorder,inorder,0,inorder.length-1);
    }

//    中序和后序遍历转二叉树
    public int postIndex = 0;

    public BTnode createTreeByPandI2(int[] inorder, int[] postorder,int inbegin,int inend) {

        if(inbegin > inend) {
            //如果满足这个条件  说明 没有左树 或者 右树了
            return null;
        }
        BTnode root = new BTnode(postorder[postIndex]);
        //找到根在中序遍历的位置
        int rootIndex = findIndexOfI(inorder,inbegin,inend,postorder[postIndex]);
        if(rootIndex == -1) {
            return null;
        }
        postIndex--;
        //分别创建右子树 和  左子树
        root.right = createTreeByPandI2(inorder,postorder,rootIndex+1,inend);

        root.left = createTreeByPandI2(inorder,postorder,inbegin,rootIndex-1);
        return root;
    }

    private int findIndexOfI2(int[] inorder,int inbegin,int inend,int key) {

        for(int i = inbegin; i <= inend;i++) {
            if(inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }
    public BTnode buildTree2(int[] inorder, int[] postorder) {
        if(postorder == null || inorder == null) return null;
        postIndex = postorder.length-1;

        return createTreeByPandI2(inorder,postorder,0,inorder.length-1);
    }














    public static void main4(String[] args) {
        // 判断一棵树是不是完全二叉树——运用层序遍历
        Binarytree T1=new Binarytree();
        T1.root= T1.CreateTree();
        boolean flag=T1.isCompleteTree(T1.root);
        System.out.println(flag);
    }



    public static void main3(String[] args) {
        Binarytree T1=new Binarytree();
        T1.root= T1.CreateTree();
        BTnode ret=T1.find2(T1.root, 'B');
        System.out.println(ret.val);
        //System.out.println(T1.getHeight(T1.root));
//        T1.find(T1.root,'B');
//
//        System.out.println(T1.tmp.val);
    }

    public static void main2(String[] args) {
        //测试返回叶子节点数目
        Binarytree T1=new Binarytree();
        T1.root= T1.CreateTree();
        int count=T1.getLeafNodeCount(T1.root);
        System.out.println(count);
        count=T1.getLeafNodeCount2(T1.root);
        System.out.println(count);
    }

    public static void main1(String[] args) {
        Binarytree T1=new Binarytree();
        T1.root= T1.CreateTree();
        System.out.println();
        T1.preOrder(T1.root);
        System.out.println();
        T1.inOrder(T1.root);
        System.out.println();
        T1.postOrder(T1.root);
        System.out.println();
        System.out.println(T1.size(T1.root));
    }

}
